package com.lg.algorithm.leetcode.dt;

public class FeiBoNaQie {

    public  static  void  main(String[] args) {

        System.out.println(F(0));
        System.out.println(F(1));
        System.out.println(F(2));
        System.out.println(F(3));
        System.out.println(F(4));
        System.out.println(F(30));

        System.out.println( " --------------- ");

        System.out.println(fib(0));
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(3));
        System.out.println(fib(4));
        System.out.println(fib(30));


    }


    public static  int F(int n){


        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        return F(n-1) + F(n-2);


    }

    public static int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;

    }

}


